<!DOCTYPE html>
<html lang="en">

<head>
	<meta charset="UTF-8">
	<meta name="viewport" content="width=device-width, initial-scale=1.0">
	<title>Document</title>
</head>

<body>
	<script>
		/* 
			一只青蛙一次可以跳上一级台阶，也可以跳上两级
			求该青蛙跳上一个n级台阶总共有多少种跳法（先后次序不同算不同的结果）
		
			一步直接跳到第n级台阶，有哪些方式
			1.在n-1级台阶跳一级
			2.在n-2级台阶处跳2级

			f(n)表示青蛙跳上n级台阶总共跳发总数
			f(n) = f(n-1) + f(n-2)

			递归类型的题目注意点：
			1.递归的终止条件（n==1一种跳法,n==2两种跳法）
			2.递归对应的递推表达式
		
			*/
		function jumpFloor(n) {
			if (n == 1) {
				return 1
			} else if (n == 2) {
				return 2;
			}
			return jumpFloor(n - 1) + jumpFloor(n - 2)
		}

		//三元
		function jumpFloor1(n) {
			return n == 1 ? 1 : n == 2 ? 2 : jumpFloor1(n - 1) + jumpFloor1(n - 2);
		}

		//记忆化递归（存储中间结果）
		//对于cache数组，cache[n]就表示fn的结果
		let cache = [, 1, 2];
		function jumpFloor2(n) {
			//找f(n)的值如果缓存存在直接用缓存
			if (cache[n] !== undefined) return cache[n]
			return cache[n] = jumpFloor2(n - 1) + jumpFloor2(n - 2)
		}

		/*
			青蛙现在可以跳一级或者n级

			f(n) = fn(n - 1) + fn(n - 2) + fn(n - 3) + .... + f(2) + f(1) + 1
		*/
		function BTjumpFloor(n) {
			if (cache[n] !== undefined) return cache[n];
			//计算fn(n)并返回
			cache[n] = 1;
			for (let i = n - 1; i >= 1; i--) {
				cache[n] += jumpFloor(i);
			}
			return cache[n];
		}

	</script>
</body>

</html>